function Node2(key = 0, color=1, left = null, right = null) {
  this.key = key
  this.color = color
  this.left = left
  this.right = right
}

let NTL = new Node2()

function Node(key =0, color=0, left =NTL, right = NTL) {
  this.key = key
  this.color = color
  this.left = left
  this.right = right
}

function RBT(rootkey) {
  this.root = new Node(rootkey, 1)
}


RBT.prototype.getNewNode = function (key) {
  return new Node(key, 0)
}

RBT.prototype.has_red_child = function(root) {
  return root.left.color == 0 || root.right.color == 0
}

RBT.prototype.insert_maintain = function(root) {
  let flag = 0
  if(root.left.color == 0 && this.has_red_child(root.left)) flag = 1
  if(root.right.color == 0 && this.has_red_child(root.right)) flag = 2
  if(flag == 0) return root
  if(root.left.color == 0 && root.right.color==0) {
    root.color = 0
    root.left.color = root.right.color = 1
    return root
  }
  if(flag == 1) {
    if(root.left.right.color == 0) {
      root.left = this.left_rotate(root.left)
    }
    root = this.right_rotate(root)
  } else {
    if(root.right.left.color == 0) {
      root.right = this.right_rotate(root.right)
    }
    root = this.left_rotate(root)
  }
  root.color = 0
  root.left.color = root.right.color = 1
  return root
}

RBT.prototype.right_rotate = function(root) {
  let temp = root.left
  root.left = temp.right
  temp.right = root
  return temp
}

RBT.prototype.left_rotate = function(root) {
  let temp = root.right
  root.right = temp.left
  temp.left = root
  return temp
}

RBT.prototype.__insert = function (root, key) {
  if(root == NTL) return this.getNewNode(key)
  if(root.key == key) return root
  if(root.key < key) root.right = this.__insert(root.right, key)
  else root.left = this.__insert(root.left, key)
  return this.insert_maintain(root)
}

RBT.prototype.insert = function(root, key) {
  root = this.__insert(root, key)
  root.color = 1
  return this.root =  root
}

RBT.prototype.erase_maintain = function(root) {
  if(root.left.color !== 2 && root.right.color !== 2) return root
  if(this.has_red_child(root)) {
    let flag = 0
    root.color  = 0
    if(root.left.color == 0) root = this.right_rotate(root),flag = 1
    else root = this.left_rotate(root), flag = 2
    root.color = 1
    if(flag == 1) root.right = this.erase_maintain(root.right)
    else root.right = this.erase_maintain(root.left)
    return root
  }
  // 二种情况讨论
  if(root.left.color == 1 && !this.has_red_child(root.left)
  || root.right.color == 1 && !this.has_red_child(root.right)) {
    root.color += 1
    root.left -= 1
    root.right -= 1
    return root  
  }
  // 注意这里color为1 不为2
  if(root.left.color == 1) {
    root.right.color = 1
    // 注意这里的操作是,只有
    if(root.left.left !== 0) {
      root.left.color = 0
      root.left = this.left_rotate(root.left)
      root.left.color = 1
    }
    root.left.color = root.color
    root = this.right_rotate(root)
  } else {
    root.left.color = 1
    // 注意这里的操作是,只有
    if(root.right.right !== 0) {
      root.right.color = 0
      root.right = this.right_rotate(root.right)
      root.right.color = 1
    }
    root.right.color = root.color
    root = this.left_rotate(root)
  }
  root.left.color = root.right.color = 1
  return root
}

RBT.prototype.__erase = function(root, key) {
  if(root == NTL) return root
  if(root.key < key) root.right = this.__erase(root.right,key)
  else if(root.key > key) root.left = this.__erase(root.left,key)
  else {
    if(root.left == NTL || root.right == NTL) {
      let temp = root.left ? root.left : root.right
      temp.color += root.color
      root = NTL
      return temp
    } else {
      let temp = this.predecessor(root)
      root.key = temp.key
      root.left = this.__erase(root.left, temp.key)
    }
  }
  return this.erase_maintain(root)
}
RBT.prototype.predecessor = function(root) {
  let temp = root.left
  while(temp.right !== NTL) temp = temp.right
  return temp
}

RBT.prototype.erase = function(root, key) {
  root = this.__erase(root,key)
  root.color = 1
  return this.root = root
}


let temp = new RBT(5)

temp.insert(temp.root,9)
temp.insert(temp.root,8)
temp.insert(temp.root,3)
temp.insert(temp.root,2)
temp.insert(temp.root,4)
temp.insert(temp.root,1)
temp.insert(temp.root,7)

// temp.erase(temp.root, 1)
// temp.erase(temp.root, 9)
temp.erase(temp.root, 5)

console.log(JSON.stringify(temp.root, null, 2))